import java.util.Objects;
import java.util.Stack;

public class Test {

    //打印
    public static void dispaly(int[]arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    //交换
    private static void swap(int[]arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //直接插入排序  升序
    public static void insertSorts(int[]arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp=arr[i];
            int j = i-1;
            for (; j >=0;j--) {
                if(tmp<=arr[j]){
                   arr[j+1]=arr[j];
                }else {
                    //如果不小于时退出，插入tmp
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }
    
    //希尔排序
    public static void shellSort(int[]arr){
       //增量
        for (int i = 5; i>0 ; i=i-2) {
            shellSortTest(i,arr);
            dispaly(arr);
        }
    }
    private static void shellSortTest(int gap,int[]arr){
        for (int i = gap; i <arr.length ; i++) {
            int tmp=arr[i];
            int j = i-gap;
            for (; j >=0 ; j=j-gap) {
                if(tmp<arr[j]){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }
    //直接选择排序
    public static void selectionSort(int[]arr){
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex=i;
            for (int j = i+1; j <arr.length ; j++) {
                if(arr[minIndex]>arr[j]){
                    minIndex=j;
                }
            }
            //交换
            swap(arr,i,minIndex);
        }
    }
    //直接选择排序 一次选两个
    public static void selectionSort1(int[]arr){
        int left=0;
        int right=arr.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <=right ; i++) {
                if(arr[maxIndex]<arr[i]){
                    maxIndex=i;
                }
                if(arr[minIndex]>arr[i]){
                    minIndex=i;
                }
            }
            //交换
            swap(arr,minIndex,left);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(arr,maxIndex,right);
            left++;
            right--;
        }
    }
    //建立大根堆
    public static void createHeap(int[]arr){
        //根节点  从下往上建堆
        for (int parent = (arr.length-1-1)/2; parent >=0 ; parent--) {
            adjust(arr,arr.length,parent);
        }
    }
    //向下调整 要有边界 建大根堆
    private static void adjust(int[]arr,int len,int parent){
        //左孩子
        int child=parent*2+1;
        while (child<len){
            //有右孩子的情况 并且右孩子大于左孩子
            if(child+1<len&&arr[child+1]>arr[child]){
                child++;
            }
            //此时child下标肯定是左右孩子中最大的
            if(arr[child]>arr[parent]){
                //交换
                swap(arr,child,parent);
                //要向下走
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }
    }
    //堆排序 升序
    public static void heapSort(int arr[]){
        //建大根堆
        createHeap(arr);
        for (int i = arr.length-1; i >0 ; i--) {
            //交换
            swap(arr,0,i);
            //向下调整
            adjust(arr,i,0);
        }
    }
    //冒泡排序
    public static void bubbleSort(int[]arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }
    //快排
    public static void quickSort(int[]arr){
        quick(arr,0,arr.length-1);
    }
    //快排
    public static void quick(int[]arr,int left,int right){
        //递归停止条件  遍历到叶子结点
        if(left>=right)return;
        //根 返回当前基准的下标，并且进行了交换操作
        int key=quickSwap(arr,left,right);
        //左 根据基准下标传值
        quick(arr,left,key-1);
        //右 根据基准下标传值
        quick(arr,key+1,right);
    }
    //根的操作  hoare
    public static int quickSwap(int[]arr,int left,int right){
        //到时候要交换基准和left元素，所以要记录left
        int i=left;
        //默认最左边left作为当前基准
        int key=arr[left];
        while (left<right){
            //先移动右边，找到小于key的元素
            while (left<right&&arr[right]>=key){
                right--;
            }
            //移动左边，找到大于key的元素
            while (left<right&&arr[left]<=key){
                left++;
            }
            //交换
            swap(arr,left,right);
        }
        //交换基准和left元素
        swap(arr,i,left);
        return left;
    }


    //快排 挖空法
    public static void quickSortHole(int[]arr){
        quickHole(arr,0,arr.length-1);
    }
    //快排
    public static void quickHole(int[]arr,int left,int right){
        //递归停止条件  遍历到叶子结点
        if(left>=right)return;
        //根 返回当前基准的下标，并且进行了交换操作
        int key=quickSwapHole(arr,left,right);
        //左 根据基准下标传值
        quick(arr,left,key-1);
        //右 根据基准下标传值
        quick(arr,key+1,right);
    }
    //挖空法
    public static int quickSwapHole(int[]arr,int left,int right){
        //默认最左边left作为当前基准
        int key=arr[left];
        while (left<right){
            //先移动右边，找到小于key的元素
            while (left<right&&arr[right]>=key){
                right--;
            }
            arr[left]=arr[right];
            //移动左边，找到大于key的元素
            while (left<right&&arr[left]<=key){
                left++;
            }
            arr[right]=arr[left];
        }
        //交换基准和left元素
        arr[left]=key;
        return left;
    }
    //快排 双指针法
    public static void quickSortPointer(int[]arr){
        quickPointer(arr,0,arr.length-1);
    }
    //快排
    public static void quickPointer(int[]arr,int left,int right){
        //递归停止条件  遍历到叶子结点
        if(left>=right)return;
        //根 返回当前基准的下标，并且进行了交换操作
        int key=quickSwapPointer(arr,left,right);
        //左 根据基准下标传值
        quick(arr,left,key-1);
        //右 根据基准下标传值
        quick(arr,key+1,right);
    }
    //双指针法
    public static int quickSwapPointer(int[]arr,int left,int right){
        int prev=left;
        int cur=left+1;
        int key=arr[left];
        while (cur<=right){
            //判断
            if(arr[cur]<key&&arr[++prev]!=arr[left]){
                swap(arr,cur,prev);
            }
            cur++;
        }
        //最后交换prev和key
        swap(arr,left,prev);
        return prev;
    }


    //三数取中法
    public static int mid(int[]arr,int left,int right){
        int mid=(left+right)>>2;
        //得到left right mid 中间数
        if(left>right){
            if(mid>left){
                return left;
            }else if(mid<right){
                return right;
            }else{
                return mid;
            }
        }else{
            if(mid<left){
                return left;
            }else if(mid>right){
                return right;
            }else {
                return mid;
            }
        }
    }
    //插入排序 要给定left和right
    public static void insertSort(int[]arr,int left,int right){
        for (int i = left+1; i <=right ; i++) {
            //存取已有序的最后一个元素
            int key=arr[i];
            int j = i-1;
            for (; j >=left ; j--) {
                if(arr[j]>key){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            //插入
            arr[j+1]=key;
        }
    }
    //快排plus版 三数取中法再快排
    public static void quickSortPlus(int[]arr){
        quickSortGroup(arr,0,arr.length-1);
    }
    //分组
    private static void quickSortGroup(int[]arr,int left,int right){
        //当最后一个节点时返回
        if(left>=right)return;
        //当趋于叶子结点时调用插入排序
        if((right-left+1)<5){
            insertSort(arr,left,right);
            return;
        }
        //得到中位数
        int mid=mid(arr,left,right);
        //交换，以arr【mid】作为基准,
        swap(arr,mid,left);

        //根 进行交换操作，并且得到基准下标 使用挖空法
        int key=quickSortSwap(arr,left,right);
        //左 根据基准分组
        quickSortGroup(arr,left,key-1);
        //右 根据基准分组
        quickSortGroup(arr,key+1,right);
    }
    //交换
    private static int quickSortSwap(int[]arr,int left,int right){
        //最左边作为基准 并且保存
        int key=arr[left];
        while (left<right){
            //先走右边 找到小于key的元素再赋值给left下标
            while (right>left&&arr[right]>=key){
                right--;
            }
            arr[left]=arr[right];
            //左边
            while (right>left&&arr[left]<=key){
                left++;
            }
            arr[right]=arr[left];
        }
        //最后给中间赋值
        arr[left]=key;
        return left;
    }

    //挖空法
    public static int quickSwapHole1(int[]arr,int left,int right){
        //默认最左边left作为当前基准
        int key=arr[left];
        while (left<right){
            //先移动右边，找到小于key的元素
            while (left<right&&arr[right]>=key){
                right--;
            }
            arr[left]=arr[right];
            //移动左边，找到大于key的元素
            while (left<right&&arr[left]<=key){
                left++;
            }
            arr[right]=arr[left];
        }
        //交换基准和left元素
        arr[left]=key;
        return left;
    }
    public static void nonRecQucikSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = mid(array,left,right);
        swap(array,left,index);
        int pivot = quickSwapHole(array,left,right);
        if(pivot-left>1) {
            stack.push(left);
            stack.push(pivot - 1);
        }

        if(right-pivot>1) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            index = mid(array,left,right);
            swap(array,left,index);
            pivot = quickSwapHole(array,left,right);
            if(pivot-left>1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(right-pivot>1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    //归并排序
    public static void mergeSort(int[]arr){
        mergeSortFun(arr,0,arr.length-1);
    }
    //部分功能
    private static void mergeSortFun(int[]arr,int left,int right){

        //1.分解
        if(left==right)return;
        int mid=(left+right)/2;
        mergeSortFun(arr,left,mid);
        mergeSortFun(arr,mid+1,right);
        //归并
        mergeSortFun1(arr,left,right,mid);
    }
    //归并
    private static void mergeSortFun1(int[]arr,int start,
                                      int end,int mid){
        int[]tmp=new int[end-start+1];
        int k=0;//用来遍历tmp数组的指针
        int s1=start;
        int e1=mid;
        int s2=mid+1;
        int e2=end;
        //可能有一边没遍历完就退出了
        while (s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                tmp[k++]=arr[s1++];
            }else {
                tmp[k++]=arr[s2++];
            }
        }
        //把剩下的全部放入tmp
        while (s1<=e1){
            tmp[k++]=arr[s1++];
        }
        while (s2<=e2){
            tmp[k++]=arr[s2++];
        }
        for (int i = 0; i < k; i++) {
            arr[i+start]=tmp[i];
        }
    }

    //非递归实现归并排序
    public static void mergeSort1(int[]arr){
        mergeSortFun1(arr,0,arr.length-1);
    }
    //部分功能
    private static void mergeSortFun1(int[]arr,int left,int right){
        int gap=1;
        while (gap<arr.length){
            for (int i = 0; i < arr.length; i+=gap*2) {
                int s1=i;
                int e1=s1+gap-1;
                if(e1>=arr.length){
                    e1=arr.length-1;
                }
                int s2=e1+1;
                if(s2>=arr.length){
                    s2=arr.length-1;
                }
                int e2=s2+gap-1;
                if(e2>=arr.length){
                    e2=arr.length-1;
                }
                mergeSortFun1(arr,s1,e2,e1);
            }
            gap*=2;
        }

    }
    //计数排序
    public static void countSort(int[]arr){
        int max=arr[0];
        int min=arr[0];
        for (int i = 0; i <arr.length ; i++) {
            if(arr[i]>max){
                max=arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        //创建数组
        int[]tmp=new int[max-min+1];
        //遍历arr
        for (int i = 0; i < arr.length; i++) {
            //给对应下标＋1
            if(arr[i]!=0){
                tmp[arr[i]-min]++;
            }
        }
        //定义arr数组下标
        int index=0;
        //遍历tmp
        for (int i = 0; i < tmp.length; i++) {
           while (tmp[i]!=0){
                arr[index++]=i+min;
                tmp[i]--;
            }
        }
    }


    public static void main(String[] args) {
       int[] arr1={ 94,94,95,92,91,93,99,97,100,98};
        dispaly(arr1);
        countSort(arr1);
        dispaly(arr1);
    }
}
